The present invention relates to a method and apparatus for communicating data among a plurality of devices. More particularly, it relates to a high performance data communication peer network.
As digital computers became more widely utilized, there arose a demand for remote users to be able to communicate with a central computer in order to supply data to or receive data from the computer system. Typically, remote users operated at terminals or similar peripheral devices each of which were connected by a dedicated line to the central computer. The central computer controlled the communication with each of these remote users and served as the repository of all the information within the system. With the advent of microprocessor technology, small independent devices became capable of performing the same data storage and manipulation as had been done previously only on large digital computers. Low cost work stations and personal computers proliferated, resulting in a vast installed base of microprocessors, minicomputers and large, general purpose computers.
Along with this decentralization of information storage and computing capabilities came immense pressure to interconnect these valuable resources, reduce costs, increase productivity and to transfer or communicate data from one computer-controlled device to another, or from one computer to another.
One known method of transferring or communicating such data is to link each pair of devices which are to communicate by a separate transmission medium of one type or another. Such a concept, while attaining the desired communication, is expensive in both the utilization of transmission media and the utilization of computing resources to control the numerous communications. For example, if four computers were to be mutually tied together using such a scheme, six separate transmission media must be used to make all the connections and each computer must monitor and control the communication activities on three communication paths. The problems of communicating using such a method are complicated further by the lack of standardization of communication protocols currently utilized by different manufacturers of computing devices.
To obtain the desired inexpensive, inter-device communication, it is known to provide a single transmission medium onto which devices are connected in order to communicate with other devices on the medium. For example, the Metcalfe et al, U.S. Pat. No. 4,063,220, discloses a bit-serial receiver-transmitter network continuously connected to all communicating devices. In such system a common transmission medium is tied to a plurality of interface stages each of which interconnects the transmission medium to a user device, such as a computer or a computer-controlled device (e.g. general purpose computer, special purpose computer, microprocessor, input-output station, remote terminal, or various other peripheral devices). Each interface stage constantly monitors the transmission medium looking for communications addressed to its associated user device.
In such known systems, communications frequently are in the form of bit-serial data packets with each data packet containing an address which identifies the intended recipient. Packets so addressed are received from the transmission medium by the interface stage and forwarded to the user device. To transmit data, the process is simply reversed and the user device transmits data to the interface stage, which in turn transmits the data along the transmission path after it has determined that the path is not in use. In this manner, each user device need monitor only one communication line, the line to and from the interface stage.
Each such interface stage communicates on the transmission medium using a communications protocol which is standard to all the interface stages on the network. Use of such networks, often called Local Area Networks, allows the sharing of expensive devices, provides common access to powerful computational facilities, and permits utilization of remote hardware, software and data base resources.
The capability of such known communication systems is necessarily limited by the bandwidth of the transmission medium. When the number of devices communicating on the transmission medium exhausts the bandwidth capability of the system, no additional devices can be connected to the system, nor can the existing devices increase their message rates.
The use of data packets for communication usually limits the amount of information which can be sent in any one transmission. The size of the data packet is determined by the network design and is not necessarily related to the content of the message. Thus, a message between two devices may require a plurality of data packets before the entire message is transmitted; or, on the other hand, a single data packet may contain more than one message between the two communicating devices. It is common within these networks for a message to be sent in two or more data packets and for the data packets to be sent in an order different than the order in which the information within the data packets comprise the message. Typically, interface stages do not attempt to decode messages in order to ensure message validity but utilize network-applied check words to determine data packet integrity. It is left to the user device to reconstruct and validate the message from the data packet(s).
In any data communication, and especially in data communication networks, it is common for the transmitter (often called the transmitting node) and receiver (or receiving node) to engage in a protocol which controls the communication process. For example, if the receiving node receives a message which is correct in format and passes the network check word tests then in use, the receiving node may send a message to the transmitting node acknowledging receipt of the valid data package. Likewise, if the data packet fails to conform to the required format, or to contain the correct checkwords, the receiving node will typically send a non-acknowledgment message or send no acknowledgement back to the transmitting node. If the transmitting node fails to receive a valid acknowledgment, it retransmits the data packet.
Even with such protocol it frequently occurs that the transmitting node and/or receiving node erroneously sends/saves a message. For example, if the acknowledgment for a valid data packet fails to reach the transmitting node, the transmitting node will retransmit the data packet. Since the receiving node has already received a valid data packet, it may treat the retransmitted data packet as a second and independent occurrence of the data packet rather than a retransmission. Consequently, there exists a need to improve the transmission protocol so that both transmitting and receiving nodes are in correspondence as to the validity of the data packet and the need for retransmission.
In generally known data communication network systems, the transmission of protocol messages (acknowledgment, non-acknowledgment, etc.) may place a burden upon the transmission medium equal to or greater than the burden of the transmission of data packets themselves. The acknowledgment or non-acknowledgment message from the receiving node must await transmission medium availability and must compete for the use of the tranmission medium with all other waiting messages. Since acknowledgment messages are usually short in length when compared to data messages, the use of separate full-length transmissions for these protocol messages is inefficient.
Current peer networks do not generally contain a method which permits packets to be assigned priority so that high priority packets can obtain access to the medium before lower priority packets. It is therefore possible and a frequent occurrence in such systems for high priority packets to wait a considerable amount of time before transmission while numerous low priority packets are transmitted.
The interface stages in such network systems generally determine whether the medium is in use by sensing the presence of the carrier frequency at which the interface stage transmits its data packets. If no carrier signal is present, the interface stage considers the medium available and proceeds to transmit the data packet. Since it takes a finite amount of time for a data packet to travel along a transmission medium, it is possible for an interface stage to sense that the carrier is not present even though some other interface stage is transmitting on the medium. In such a situation, both interface stages will be transmitting at the same time on the same medium and hence the data packets will interfere with each other and become unintelligible. Upon the occurrence of this interference, called a collision, the interface stages must detect the collision and retransmit the message at a later time.
In systems such as disclosed in the Metcalfe et al patent, the later time can be determined by reference to a back-off timer which randomly generates a number representing a period of time in which the interface stage does not attempt to transmit on the medium. Unfortunately, since the interface stages are usually constructed identically, the back-off timers frequently generate the same back-off delay period and the recollision may occur. Moreover, back-off timers may not take into account the priority of the data packets and the lower priority packets may be given first access to the transmission medium.
The recent advances in microelectronics technology have caused a significant decrease in the cost of communicating devices. Accordingly, it is important to decrease the cost of the transmission medium which interconnect such communicating devices in a network system. Coaxial cable is frequently used as the transmission medium in such network systems. However, efforts to reduce system cost by the use of cheaper coaxial cable are often thwarted by the capacitive charateristics of low cost coaxial cable which distort data packet content and cause variations in the amplitude of a transmitted data packet's waveform.
In generally known network systems, the protocols apply between a single receiver and a single transmitter and communication may not be possible between a single transmitter and multiple receivers because the use of the protocol would involve multiple receivers simultaneously sending acknowledgment messages.
It is accordingly an object of the present invention to provide a novel method and a communication protocol for assuring proper data packet receipt and storage.
It is yet another object of the present invention to provide a novel method and system for transmitting data packets along a data communication network in accordance with the priority of the data packet.
These and many other objects and advantages of the present invention will be apparent to one skilled in the art from the claims and from the following detailed description when read in conjunction with the appended drawings.